package airthmetic.exercise.tree.avl;

public class AvlTree {
    AvlNode root;

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("该树的前序遍历结果为:");
        preOrder(root, sb);
        sb.append("该树的中序遍历结果为:");
        inOrder(root, sb);
        sb.append("该树的后序遍历结构为:");
        postOrder(root, sb);
        return sb.toString();
    }

    private void inOrder(AvlNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        inOrder(node.left, sb);
        sb.append(node.key).append("->");
        inOrder(node.right, sb);
    }

    private void preOrder(AvlNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        sb.append(node.key).append("->");
        preOrder(node.left, sb);
        preOrder(node.right, sb);
    }

    private void postOrder(AvlNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        postOrder(node.left, sb);
        postOrder(node.right, sb);
        sb.append(node.key).append("->");
    }


    public int getHeight(AvlNode avlNode) {
        return avlNode == null ? 0 : avlNode.height;
    }

    /**
     * LL旋转：对失衡节点进行右旋
     *       30           20
     *      /  \         /  \
     *     20  40       10  30
     *    /  \         /   /  \
     *   10  25       5  25  40
     *  /
     * 5
     *
     * @param unbalance
     * @return
     */
    public AvlNode LLrotate(AvlNode unbalance) {
        AvlNode newRoot = unbalance.left;
        unbalance.left = newRoot.right;
        newRoot.right = unbalance;

        unbalance.height = Math.max(getHeight(unbalance.left), getHeight(unbalance.right)) + 1;
        newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;
        return newRoot;
    }

    /**
     * RR旋转:对失衡节点进行左旋
     *        20                        30
     *       /  \                      /  \
     *      10  30                   20   40
     *         /  \                 /  \    \
     *       25   40               10  25   50
     *              \
     *              50
     *
     * @param unbalance
     * @return
     */
    public AvlNode RRrotate(AvlNode unbalance) {
        AvlNode newRoot = unbalance.right;
        unbalance.right = newRoot.left;
        newRoot.left = unbalance;

        unbalance.height = Math.max(getHeight(unbalance.left), getHeight(unbalance.right)) + 1;
        newRoot.height = Math.max(getHeight(newRoot.left), getHeight(newRoot.right)) + 1;
        return newRoot;
    }


    /**
     * LR旋转:对失衡节点左子树进行左旋，再对失衡节点进行右旋
     *
     * @param unbalance
     * @return
     */
    public AvlNode LRrotate(AvlNode unbalance) {
        unbalance.left = RRrotate(unbalance.left);
        AvlNode newRoot = LLrotate(unbalance);
        return newRoot;
    }

    public AvlNode RLrotate(AvlNode unbalance) {
        unbalance.right = LLrotate(unbalance.right);
        AvlNode newRoot = RRrotate(unbalance);
        return newRoot;
    }

    public void insert(int key) {
        this.root = insert(this.root, key);
    }

    public AvlNode insert(AvlNode node, int key) {
        // terminal
        if (node == null) {
            node = new AvlNode(key);
            return node;
        }

        if (key > node.key) {
            node.right = insert(node.right, key);

            if (Math.abs(getHeight(node.left) - getHeight(node.right)) > 1) {
                if (key > node.right.key) {
                    // RR情况
                    node = RRrotate(node);
                } else {
                    // RL情况
                    node = RLrotate(node);
                }
            }


        } else if (key < node.key) {
            node.left = insert(node.left,key);
            if (Math.abs(getHeight(node.left) - getHeight(node.right)) > 1) {
                if (key < node.left.key) {
                    // LL情况
                    node = LLrotate(node);
                } else {
                    // LR情况
                    node = LRrotate(node);
                }
            }
        } else {// 相等不做处理

        }

        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;

        return node;
    }


    class AvlNode {
        int key;
        AvlNode left;
        AvlNode right;

        int height;

        public AvlNode(int key) {
            this.key = key;
            height = 1;
        }


        @Override
        public String toString() {
            return "AvlNode{" +
                    "key=" + key +
                    ", left=" + left +
                    ", right=" + right +
                    ", height=" + height +
                    '}';
        }
    }


}
